package ua.mykola.dynamicp;

public class RecursiveAppoximateStringMatcher {

	static final int MATCH = 0;
	static final int INSERT = 1;
	static final int DELETE = 2;

	public int editDistance(String stringIn, String string2In) {
		String string = " " + stringIn;
		String string2 = " " + string2In;
		return editDistance(string.toCharArray(), string2.toCharArray(), string.length() - 1, string2.length() - 1);
	}

	private int editDistance(char[] s, char[] t, int i, int j) {
		if (i == 0)
			return (j * indel(' '));
		if (j == 0)
			return (i * indel(' '));

		int[] opt = new int[3];
		/* cost of the three options */
		opt[MATCH] = editDistance(s, t, i - 1, j - 1) + match(s[i], t[j]);
		opt[INSERT] = editDistance(s, t, i, j - 1) + indel(t[j]);
		opt[DELETE] = editDistance(s, t, i - 1, j) + indel(s[i]);

		int lowest_cost;
		lowest_cost = opt[MATCH];
		int k;
		for (k = INSERT; k <= DELETE; k++)
			if (opt[k] < lowest_cost)
				lowest_cost = opt[k];

		return lowest_cost;
	}

	private int match(char c, char d) {
		if (c == d)
			return 0;
		else
			return 1;
	}

	private int indel(char c) {
		return 1;
	}
}
